题解 P3618 【误会】

发表于 | 更新于

题意:对于一句原句和听到的句子，理解方式是将听到的句子替换掉原句的相同部分，替换成$*$，使得原句形成一个新的句子，以达到新的意思，你的任务是统计有多少种意思

$dp+hash$

设子串长度为$m$，$f_{i}$表示到子串末尾在原句是第$i$个位置有几种方案，显然对于每个$f_{i}$有三种情况，当原句以$i$结尾的长度为$m$的字符串等于子串$f_{i}=f_{i-1}+f_{i-m}$,即选或不选，否则$f_{i}=f_{i-1}$,只能不选；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int p=313;
int v=1,T,n,m,a[2000000];
ull power[2000000],sum[2000000],f[200000],t;
char s1[200000],s2[200000];
int main(){
    scanf("%d",&T);
    power[0]=1;
    for (int i=1;i<=100001;i++) power[i]=power[i-1]*p;
    while (v<=T){
        scanf("%s\n%s",s1+1,s2+1);
        memset(f,0,sizeof(f));
        n=strlen(s1+1);m=strlen(s2+1);t=0;
        for (int i=1;i<=n;i++) 
            sum[i]=sum[i-1]*p+s1[i]-96;
        for (int i=1;i<=m;i++)
            t=t*p+s2[i]-96;
        f[0]=1;
        for (int i=1;i<=n;i++)
            if (t==sum[i]-sum[i-m]*power[m])
                f[i]=(f[i-1]+f[i-m])%1000000007;
            else f[i]=f[i-1];
        printf("Case #%d: %d\n",v,f[n]);
        v++;
    }
}